package com.wtgroup.demo.mianshi.算法.链表;

import com.wtgroup.demo.common.bean.LinkNode;
import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;

import java.util.Stack;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/2 10:47
 */
public class Q_链表是否回文 {
    public static void main(String[] args) {
        Judger.of(() -> {
                    LinkNode head = mockPalinLinkList();

                    boolean res = new S3().doit(head);
                    if (!res) {
                        if (head != null) head.print();
                        else System.out.println("nullllllllllll");
                    }
                    return res == true;
                })
                .setIterCount(10000)
                .start()
                .print();
    }

    /**
     * 笔试用
     */
    static class S1 {
        boolean doit(LinkNode head) {
            Stack<LinkNode> stack = new Stack<>();
            LinkNode curr = head;
            while (curr != null) {
                stack.push(curr);
                curr = curr.next;
            }
            curr = head;
            while (stack.isEmpty() == false) {
                LinkNode pop = stack.pop();
                if (curr.value != pop.value) {
                    return false;
                }
                curr = curr.next;
            }
            return true;
        }
    }

    static class S2 {
        /*
         1. 快慢指针, 定位到中间节点
         2. 右边一半入栈, 和左半段对比
         */
    }

    /**
     * 面试用
     * 右半段反转
     * 空间 O(1)
     */
    static class S3 {
        boolean doit(LinkNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            // 定位到中间位置, 奇数中间, 偶数上中点
            LinkNode midNode = Q_链表中点.getMiddleNode(head);

            LinkNode rhead = midNode.next;
            midNode.next = null;

            LinkNode newNext = null;

            LinkNode rheadNextBackup = rhead.next;
            rhead.next = newNext;

            while (rheadNextBackup != null) {
                newNext = rhead;
                rhead = rheadNextBackup;
                rheadNextBackup = rhead.next;
                rhead.next = newNext;
            }

            LinkNode le = head, ri = rhead;
            while (le != null && ri != null && le.value == ri.value) {
                le = le.next;
                ri = ri.next;
            }

            // 只要一边的链结束了
            return le == null || ri == null;
        }


    }

    static LinkNode mockPalinLinkList() {
        int len = RandomUtil.randomInt(1, 1000);
        int[] ints = RandomUtil.randomArray(len, 0, 100);
        LinkNode head = null;
        LinkNode tail = head;
        for (int i = 0; i < ints.length; i++) {
            if (head == null) {
                tail = head = new LinkNode(ints[i]);
            } else {
                tail = tail.next = new LinkNode(ints[i]);
            }
        }
        if (tail != null) {
            // 逆向追加, 得出的链表一定是回文的
            boolean odd = RandomUtil.randomInt(1, 10) < 5;
            for (int i = ints.length - (odd ? 1 : 2); i >= 0; i--) {
                tail = tail.next = new LinkNode(ints[i]);
            }
        }
        return head;
    }


}
